|
Chris Pollett >Old Classes
> |
HW#3 --- last modified March 02 2019 17:05:06..Due date: Oct 27
Files to be submitted: Purpose: To gain experience with how heap files are implemented in DBMS's, to code the LRU buffer replacement policy, and to understand query evaluation and external sorting. Specification: First, do problems 12.5 and 13.3 and submit them in TextbookProblems.pdf. The coding part of the assignment consists of taking the code below and modifying it so that it supports Linked-List of Pages Heap Files as describe on page 325 of the book and so that one can create BufferManager's that use the Least Recently Used page replacement policy. To be more specific I want you to create subclasses HeapMockDisk and LRUBufferManager of the MockDisk and BufferManager classes below. To make HeapMockDisk I want you to extend MockDisk and add the following methods: public void deleteFile(String fileName) throws MissingResourceException /* this deletes a file from the directory and deallocates its blocks from the PAM. It throws a MissingResourceException if the filename is not found in the directory. */ public String toStringFile(String fileName) throws MissingResourceException /* This returns a string containing each record in a file, one newline after each record. To draw a record it prints the bytes in the record separated by spaces. For example, suppose the file had record size of 3 byte and two records in it. a possible string returned might be: "255 0 148\n192 16 12" It throws a MissingResourceException if the filename is not found in the directory. */ public void addRecord(String fileName, byte[] record) throws MissingResourceException, IllegalArgumentException /* Adds the given record to the given heap file Should use the available pages linked list as described in the book. If the page becomes full after the addition, page should be moved to the full pages linked list. It throws a MissingResourceException if the filename is not found in the directory. It throws an IllegalArgumentException if the record contains more bytes then the record size of the given heap file. */ public void deleteRecord(String fileName, byte[] record) throws MissingResourceException, IllegalArgumentException /* Delete the given record from the given heap file Should check both the available pages linked list and the full pages linked list for the record. If a full page becomes un-full after the deletion, page should be moved available pages linked list. If a page becomes empty it should removed from the file. The method throws a MissingResourceException if the filename is not found in the directory or the record is not found in the file. It throws an IllegalArgumentException if the record contains more bytes then the record size of the given heap file. */ To create the class LRUBufferManager, I expect you to override the two methods getPage and releasePage of the BufferManager class so that they implement an LRU page replacement policy. To get some idea how the code below works, it is instructive to read the comments in it. It is also useful to compile the code and run it. To do this cut and paste the three classes into different files named after their respective class names. Alternatively, you can download the code using the link Hw3.zip. Then compile the code using: javac MockDisk.java and run it using java MockDisk. The program as it stands should do some simple operations on the MockDisk and print out the current contents of the drive together with some data associated with the drive. You can make similar kinds of tests to make sure your code works by overriding main in your subclass. (Bonus 2pts) Write a robust set of tests for your code using JUnit. Submit these in the file Test.zip along with a readme for how to build and use your tests. Note if you're uninterested in the bonus, then just submit a blank file for this file.
//MockDisk.java
import java.nio.*;
/**
This class is used to emulate an imaginary disk drive. The drive consists
of 128 pages each of 6 bytes in length.
Page 0 is always used for the start of the directory of heap
files stored in the drive. Pages in the directory are stored
in Header Page format. @see Page
The directory consists of a linked list of header pages for different
heap files stored in the drive. The last page of the directory is marked
by the fact that its next link is null (i.e., 0).
Header pages in the directory are considered to be deleted files
if there full pages list link is the null pointer.
To mark a page as deleted one should of course also delete
all of the pages associated with it (but not the header page itself)
in the PAM. To create a heap file with no data pages
the full pages list link should be set to EMPTY_PAGE (128).
Pages 123 - 127 are used to contain a Page Allocation Map
(PAM). Data bytes in these pages are used to indicate which
pages on the drive have been allocated. The four data bytes
of page 123 indicate the allocation of the first 32 blocks of
the drive; page 124 the next 32 blocks, etc.
@see Page
@author Chris Pollett
@version 2003/10/6
*/
public class MockDisk
{
/**
default constructor. Allocates memory for pages in disk drive.
creates a buffer manager and initializes it. lastly formats the drive.
*/
public MockDisk()
{
Page[] drive = new Page[LAST_DISK_PAGE + 1];
for(int i=0; i<=LAST_DISK_PAGE; i++)
{
drive[i] = new Page();
}
driveBuffer = new BufferManager();
driveBuffer.create(BUFFER_SIZE, drive);
format();
}
/**
does the same as the default contructor but allows one
to specify a BufferManager to use. Useful if want to
subclass BufferManager to do a customized page replacement policy.
@param buffer - buffer manager to use in creating this instance
of the drive
*/
public MockDisk(BufferManager buffer)
{
Page[] drive = new Page[LAST_DISK_PAGE + 1];
for(int i=0; i<=LAST_DISK_PAGE; i++)
{
drive[i] = new Page();
}
driveBuffer = buffer;
driveBuffer.create(BUFFER_SIZE, drive);
format();
}
/**
clears all pages in the drive. Creates the PAM and directory pages
and allocates these pages in the PAM.
*/
public void format()
{
Page p;
byte zero = 0;
// erase all the pages
for(int i = 0; i <= LAST_DISK_PAGE ; i++)
{
p = driveBuffer.readPage(i);
for(int j = 0; j < PAGE_SIZE; j++)
{
p.setByte(j , zero);
}
driveBuffer.setDirty(i);
driveBuffer.releasePage(i);
}
int previousPage = NULL_PAGE;
int nextPage;
//set next and previous page links in PAM
for(int i = PAM_START; i <= PAM_END; i++)
{
p = driveBuffer.readPage(i);
p.setPreviousPage(previousPage);
nextPage = (i < LAST_DISK_PAGE) ? i + 1 : NULL_PAGE;
p.setNextPage(nextPage);
previousPage = i;
driveBuffer.setDirty(i);
driveBuffer.releasePage(i);
}
//allocate pages in PAM and for start of directory
for(int i = PAM_START; i <= PAM_END; i++)
{
allocatePage(i);
}
allocatePage(DIR_START);
}
/**
sets the page allocation bit of the given page in the PAM
to true. i.e., allocated
@param pageNumber - number of page to allocate
*/
public void allocatePage(int pageNumber)
{
setPageAllocation(pageNumber, true);
}
/**
sets the page allocation bit of the given page in the PAM
to false. i.e., not allocated
@param pageNumber - number of page to be deallocated
*/
public void deallocatePage(int pageNumber)
{
setPageAllocation(pageNumber, false);
}
/**
sets the page allocation bit of the given page in the PAM
to the supplied value
@param pageNumber - number of page to be set
@param allocate - boolean of whether to allocate (true) or
deallocate (false)
*/
public void setPageAllocation(int pageNumber, boolean allocate)
{
isValidNumber(pageNumber, 0, LAST_DISK_PAGE);
int pagesPerPAMPage = DATA_SIZE << 3; // DATA_SIZE * 8
int whichByte = DATA_START + ((pageNumber >> 3) % DATA_SIZE);
int currentIndex = PAM_START;
Page currentPage = driveBuffer.readPage(currentIndex);
for(int i = PAM_START; i < PAM_START + pageNumber/pagesPerPAMPage; i++)
{
driveBuffer.releasePage(currentIndex);
currentIndex = currentPage.getNextPage();
currentPage = driveBuffer.readPage(currentIndex);
}
int whichBit = pageNumber & 7;
if(allocate)
{
currentPage.setByte(whichByte, (byte)(currentPage.getByte(whichByte)
| (1 << whichBit)));
}
else
{
currentPage.setByte(whichByte, (byte)(currentPage.getByte(whichByte)
& ~(1 << whichBit)));
}
driveBuffer.setDirty(currentIndex);
driveBuffer.releasePage(currentIndex);
}
/**
Used to create an empty heap file and add it to the drive directory
<b> Warning does not check if file already exists!!</b>
@param name - two byte name of heap file
@param recordSize
*/
public void createFile(String name, int recordSize)
throws BufferOverflowException, IndexOutOfBoundsException
{
int length = name.length();
isValidNumber(length, 0, DATA_SIZE-2);
//filenames at most DATA_SIZE-1 chars
isValidNumber(recordSize, 1, DATA_SIZE);
Page p;
int j;
int i;
boolean notAddedName = true;
int currentDirIndex;
int next = DIR_START;
while(notAddedName)
{
currentDirIndex = next;
p = driveBuffer.readPage(currentDirIndex);
if(isNullPage(p.getByte(HEADER_FULL_INDEX)))
/* checks if header page not in
use: either just allocated or a deleted file.
If yes then use it to create file.
If page in use then this byte will either point to
a list of full data pages in the given heap file
or will point to EMPTY_PAGE, if the full page list is
empty.
*/
{
notAddedName = false;
for(i = DATA_START, j=0; i < DATA_START + length; i++, j++)
{
p.setByte(i, (byte)name.charAt(j) );
}
driveBuffer.setDirty(currentDirIndex);
p.setByte(HEADER_FULL_INDEX, (byte)EMPTY_PAGE);
p.setByte(HEADER_AVAILABLE_INDEX, (byte)DIR_START);
//indicates the size of records in this file
p.setRecordSize(recordSize);
}
next = p.getNextPage();
// check if need to extend directory for one more file
if(notAddedName && isNullPage(next))
{
appendPage(currentDirIndex, firstFreePage());
next = p.getNextPage();
}
driveBuffer.releasePage(currentDirIndex);
}
}
/**
Computes the first not allocated page listed in the PAM
return - page number of a free page
*/
public int firstFreePage() throws BufferOverflowException
{
boolean notFound = true;
Page p;
int currentIndex = PAM_START;
int j;
int data = 0;
int cnt = 0;
while( notFound && cnt <= LAST_DISK_PAGE)
{
p=driveBuffer.readPage(currentIndex);
j = DATA_START-1;
while(j < PAGE_SIZE - 1 && notFound)
{
j++;
data = p.getByte(j) &255;
if(data < 255) notFound=false;
cnt += 8;
}
driveBuffer.releasePage(currentIndex);
currentIndex++;
}
if(notFound) throw new BufferOverflowException();
cnt -= 8;
j=0;
while((data | (1<<j)) == data)
{
j++;
cnt++;
}
return cnt;
}
/**
Creates a string with details of the current drive state
@return - string with details
*/
public String toStringDrive()
{
String out = "";
out += "Drive's directory:\n";
out += toStringDirectory();
out += "Page Allocation Map (PAM) \n";
out += "Each row gives current allocation of eight pages.\n";
out += "First row starts with Page 0.\n";
out += toStringPAM();
out +="\nData View of the contents of each page:\n";
out += toStringPages(0, LAST_DISK_PAGE);
return out;
}
/**
Creates a string with details of the heap files stored
in the drives directory
@return - string with details
*/
public String toStringDirectory()
{
boolean notEnd =true;
int currentDirIndex = DIR_START;
int next;
int i = 0;
Page p;
String out ="";
while( notEnd )
{
p = driveBuffer.readPage(currentDirIndex);
next = p.getNextPage();
notEnd = !isNullPage(next);
out += "File " + i + ": " + p.toStringHeaderPage() + "\n";
driveBuffer.releasePage(currentDirIndex);
currentDirIndex = next;
i++;
}
return out;
}
/**
Creates a string with details of which blocks
the PAM thinks are allocated and which not
@return - string with details
*/
public String toStringPAM()
{
Page p;
int j = 0;
int currentPAMPage = PAM_START;
int bytesLeft = PAM_SIZE;
int nextPage;
int tmp;
String out="";
while(!isNullPage(currentPAMPage))
{
p = driveBuffer.readPage(currentPAMPage);
tmp = (bytesLeft > DATA_SIZE) ? DATA_SIZE : bytesLeft;
for(int i = DATA_START; i < DATA_START+tmp; i++)
{
out += p.toStringByte(i) + "\n";
}
nextPage = p.getNextPage();
driveBuffer.releasePage(currentPAMPage);
currentPAMPage = nextPage;
bytesLeft -= DATA_SIZE;
}
return out;
}
/**
Creates a string which lists out the contents of
a sequence of data pages from the drive
@return - the string with contents
*/
public String toStringPages(int low, int high)
{
Page p;
String out = "";
for(int i = low; i <= high; i++)
{
out += "Page " + i + ": ";
p = driveBuffer.readPage(i);
out += p.toStringDataPage() +"\n";
driveBuffer.releasePage(i);
}
return out;
}
/* END PUBLIC METHODS */
/**
Appends the page next to the page node
in a heap file. It is assumed that
page next should have no data (newly allocated).
So its record count is set to zero. Further
next's next link is set to null
@param node - page that will append to
@param next - page that is being appended
*/
void appendPage(int node, int next)
{
isValidNumber(node, 0, LAST_DISK_PAGE);
isValidNumber(next, 0, LAST_DISK_PAGE);
allocatePage(next);
Page p = driveBuffer.readPage(node);
p.setNextPage(next);
driveBuffer.setDirty(node);
driveBuffer.releasePage(node);
p = driveBuffer.readPage(next);
p.setPreviousPage(node);
p.setNextPage(NULL_PAGE);
p.setNumberOfRecords(0);
driveBuffer.setDirty(next);
driveBuffer.releasePage(next);
}
/**
Checks if the given pageNumber is a null page.
0 is the null page.
@param pageNumber - page to check if null pointer
@return - whether or not was zero page
*/
boolean isNullPage(int pageNumber)
{
return (pageNumber == NULL_PAGE);
}
/**
Used with header pages @see Page of heap files. Is used to
check that the give heap file has an empty full pages list
but the file is not marked for deletion.
@param pageNumber - page index to check
@return - whether page number is the EMPTY_PAGE
*/
boolean isEmptyPage(int pageNumber)
{
return (pageNumber == EMPTY_PAGE);
}
/**
Checks if number is <=high and >= low. If not throws an
IndexOutofBoundsException. Method says which class it belongs
to (maybe could have avoided code duplication)
@param number - number to check
@param low - low value of range number should be in
@param high - high value of range number should be in
@throws IndexOutOfBoundsException - returned if number not in range
*/
static void isValidNumber(int number, int low, int high)
throws IndexOutOfBoundsException
{
if(number > high || number < low)
throw new IndexOutOfBoundsException(
"(MockDisk Index Exception) Number was:" +
number + ".\n Maximum allowable is: " + high +
".\n Minimum allowable is: " + low + ".\n");
}
/*
Some simple tests to illustrate how the drive works.
*/
public static void main(String args[])
{
MockDisk m = new MockDisk();
m.createFile("hi",1);
m.createFile("yo",2);
m.createFile("ho",3);
m.createFile("h2",4);
System.out.println(m.toStringDrive());
for(int i=0; i < BUFFER_SIZE; i++)
{
System.out.println(m.driveBuffer.toStringBufferPoolPage(i));
}
}
public final static int LAST_DISK_PAGE = Page.MAX_PAGE_INDEX;
//index of last page stored in drive
public final static int BUFFER_SIZE = 4;
// number of pages in the buffer pool the buffer manager has
public final static int PAGE_SIZE = Page.PAGE_SIZE;
// size of a disk page in bytes
public final static int DATA_SIZE = Page.DATA_SIZE;
// number of bytes of data that can be stored in a disk page
public final static int DATA_START = PAGE_SIZE - DATA_SIZE ;
// byte offset to first data byte in a page.
public final static int PAM_SIZE = (LAST_DISK_PAGE+1)/8;
//Number of bytes of data needed for PAM
public final static int PAM_START = LAST_DISK_PAGE-(PAM_SIZE+1)/DATA_SIZE;
//first page of PAM
public final static int PAM_END = LAST_DISK_PAGE;
//Size of PAM in bytes
public final static int HEADER_FULL_INDEX = PAGE_SIZE-1;
// index of the byte used in a header page to store a link to the list
// of full pages in a heap file
public final static int HEADER_AVAILABLE_INDEX = PAGE_SIZE-2;
// index of the byte used in a header page to store a link to the list
// of avilable pages (those that can store more records) in a heap file
public final static int EMPTY_PAGE = 128;
// used ot indicate a heap files full page list is empty
// but the file is not deleted.
public static int DIR_START = 0;
//Location of directory in drive
public static int NULL_PAGE = 0;
//Next/prev page pointing into Directory
//indicates no next/prev page.
BufferManager driveBuffer;
// buffer used to manage disk I/Os
}
//BufferManager.java
import java.nio.*;
import java.util.*;
/**
This class is used to manage reading and writing pages on a
MockDisk object. All read requests from a MockDisk should go
through the drive's BufferManager object: driveBuffer.
To get a reference to the page numbered i, one calls
Page p = driveBuffer.readPage(i);
This pins the page in the BufferManager's buffer pool. So
when one is done with the page one has to call
driveBuffer.releasePage(i);
If one has a reference to a page via the buffer and one wants
to change the page then it is the user of the pages responsibility
to set the dirty bit of the page so that the BufferManager knows
to write the page back to disk if it gets replaced from the buffer.
To set the dirty bit one does:
driveBuffer.setDirty(i);
BEFORE releasing the page.
@author Chris Pollett
@version 2003/10/6
*/
public class BufferManager
{
/**
Empty constructor. Set-up of class deferred to create method below
*/
public BufferManager()
{
}
/**
Sets up the BufferManager creates the bufferPool,
and arrays to keep track pin count, dirtiness and which
pages are in the pool. Sets the passed drive full of free
pages to be the pages managed by this BufferManager.
@param size - how many pages the buffer pool will be
@param drive - pages used to represent the disk drive
*/
public void create(int size, Page[] drive)
{
bufferSize = size;
bufferPool = new Page[size];
pinCount = new int[size];
pageNumbers = new int[size];
dirty = new boolean[size];
this.drive=drive;
storedPages= new Hashtable();
driveSize = drive.length;
clock = 0;
for(int i = 0; i < size; i++)
{
bufferPool[i] = new Page();
}
}
/**
Tries to find requested page in buffer pool and if so
updates the pin count of the page and returns a
reference to it. If not it uses getPage to swap the page
into the buffer pool.
@param pageNumber - which page of drive to return
@throws IndexOutOfBoundsException - thrown if pageNumber not in drive
@return - requested page
*/
public Page readPage(int pageNumber) throws IndexOutOfBoundsException
{
isValidNumber(pageNumber, 0, driveSize);
Object indexObj=storedPages.get(new Integer(pageNumber));
int index;
if(indexObj == null)
{
index = getPage(pageNumber);
pinCount[index] = 1;
}
else
{
index = ((Integer)indexObj).intValue();
pinCount[index]++;
}
return bufferPool[index];
}
/**
Sets the dirty bit of the indicated page. The dirty bit being
set indicates that if the page is removed from the buffer
it must be first written back to disk.
@param pageNumber - page whose dirty bit needs to be set
@throws MissingResourceException - thrown if page not currently in buffer
*/
public void setDirty(int pageNumber) throws MissingResourceException
{
isValidNumber(pageNumber, 0, driveSize);
Object indexObj=storedPages.get(new Integer(pageNumber));
if(indexObj == null)
throw new MissingResourceException("Page not in buffer pool.",
"BufferManager", ""+pageNumber);
dirty[((Integer)indexObj).intValue()] = true;
}
/**
Releases one pin on the given page in the buffer pool.
@param pageNumber - page to release a pin of.
@throws IllegalStateException - if pin count on a page goes negative.
*/
public void releasePage(int pageNumber)
throws IllegalStateException
{
isValidNumber(pageNumber, 0, driveSize);
Object indexObj = storedPages.get(new Integer(pageNumber));
if(indexObj == null)
throw new MissingResourceException("Page not in buffer pool.",
"BufferManager", ""+pageNumber);
int index =((Integer)indexObj).intValue();
if(pinCount[index] <= 0)
throw new IllegalStateException("Page "+pageNumber
+ "released too many times");
pinCount[index]--;
}
/**
Gets a page that is not currently in the buffer pool.
If the page that is replaced has its dirty bit
set then it is written back to the disk. This
method uses the clock replacement policy to determine
which should be the next buffer page to be used
to read disk page into. For the Homework you should
override this method to use the LRU policy.
@param pageNumber - page to retrieve.
@throws BufferOverflowException - if page is not in buffer and
all buffer pages are currently pinned.
*/
int getPage(int pageNumber)
throws BufferOverflowException
{
isValidNumber(pageNumber, 0, driveSize);
int index = clock + 1;
index = (index < bufferSize) ? index : 0;
while( index != clock && pinCount[index] > 0)
{
index++;
index = (index < bufferSize) ? index : 0;
}
if( pinCount[index] > 0)
throw new BufferOverflowException();
if(dirty[index])
{
drive[pageNumbers[index]].copy(bufferPool[index]);
dirty[index] = false;
}
storedPages.remove(new Integer(pageNumbers[index]));
bufferPool[index].copy(drive[pageNumber]);
pageNumbers[index] = pageNumber;
storedPages.put(new Integer(pageNumber), new Integer(index));
pinCount[index] = 1;
clock++;
clock = (clock < bufferSize) ? clock : 0;
return index;
}
/**
Generates a String to represent the data stored about a given page
in the buffer pool. i.e., which disk page, its pin count,
its dirtyness and its data.
@return the string with this information
*/
public String toStringBufferPoolPage(int i)
{
isValidNumber(i, 0, bufferSize-1);
String out = "";
out += "Buffer Page: " + i + " pageNumber: "+ pageNumbers[i];
out += " pinCount: "+ pinCount[i] + " dirty: " + dirty[i] +"\n";
out += "\t"+bufferPool[i].toStringDataPage();
return out;
}
/**
Checks if number is <=high and >= low. If not throws an
IndexOutofBoundsException. Method says which class it belongs
to (maybe could have avoided code duplication)
@param number - number to check
@param low - low value of range number should be in
@param high - high value of range number should be in
@throws IndexOutOfBoundsException - returned if number not in range
*/
static void isValidNumber(int number, int low, int high)
throws IndexOutOfBoundsException
{
if(number > high || number < low)
throw new IndexOutOfBoundsException("(Buffer Index Exception)" +
"Number was:" + number +".\n Maximum allowable is: " + high +
".\n Minimum allowable is: " + low + ".\n");
}
int driveSize; // size in number of pages in the drive
int bufferSize; // size in number of pages in the buffer pool
int clock; /*keeps track of where the clock is at in terms of cycling
through pages in the buffer pool for clock replacement
buffer policy */
Page[] bufferPool; // pages used for the buffer
Page[] drive; // the actual pages in the disk drive
int[] pinCount; // used to keep track of the number of times a
// page has been pinned
int[] pageNumbers; // used to keep track of which page a given
// buffer stores
boolean[] dirty; // used to keep track of which buffer pages are dirty
Hashtable storedPages; // used to quickly look-up via drive page number
// where a give page is stored in the buffer pool
}
//Page.java
/**
This class is used to represent one page of our MockDisk disk drive
There are two kinds of pages used in our mock disk drive, both of
which use instances of this class to store: data pages and header pages.
For more robust purposes might have used subclassing.
In a data page the bytes are arranged as
byte# Use
0 low order seven bits - next page link
high order bit is high order bit of record count
1 low order seven bits - previous page link
high order bit is low order bit of record count
2-5 data bytes
As mentioned above the two high order bits combine together
to form a two bit number indicating how many records are stored
in this data page.
Data pages are used to store the data in a heap file as well as
being used in the PAM.
In a header page the bytes are arranged as
byte# Use
0 low order seven bits - next page link
high order bit is high order bit of record count
1 low order seven bits - previous page link
high order bit is low order bit of record count
2-3 file name
4 pageNumber of the list of pages with available space
in this heap file
5 pageNumber of the list of pages which are full
in this heap file
As mentioned above the two high order bits combine together
to form a two bit number indicating the record size in bytes
used in this heap file.
Header pages are used in the drive directory. If byte
5 is set to 0 (NULL_PAGE). It indicates this file is deleted.
If byte 5 is set to 128 (EMPTY_PAGE). It indicates the
full page list is empty but the file is still in use
(not deleted).
@author Chris Pollett
@version 2003/10/6
*/
public class Page
{
/**
Allocates memory for the bytes of this page
*/
public Page()
{
data = new byte[PAGE_SIZE];
}
/**
Copy constructor for this class
@param p - Page to be copied
*/
public Page(Page p)
{
data = new byte[PAGE_SIZE];
copy(p);
}
/**
Copies the page p into the current page object
@param - page to be copied
*/
public void copy(Page p)
{
for(int i=0; i < PAGE_SIZE; i++)
{
data[i] = p.data[i];
}
}
/**
Gives an integer reference to the next page in the file after
this page.
@return - index of the next page
*/
public int getNextPage()
{
return data[0] & MAX_PAGE_INDEX;
}
/**
sets the next page link off this page to the indicated value
@param pageNumber
*/
public void setNextPage(int pageNumber)
{
isValidNumber(pageNumber, 0, MAX_PAGE_INDEX);
data[0] &=MASK;
data[0] += (byte)pageNumber;
}
/**
Gives an integer reference to the previous page in the file before
this page.
@return - index of the next page
*/
public int getPreviousPage()
{
return data[1] & MAX_PAGE_INDEX;
}
/**
sets the previous page link off this page to the indicated value
@param pageNumber
*/
public void setPreviousPage(int pageNumber)
{
isValidNumber(pageNumber, 0, MAX_PAGE_INDEX);
data[1] &=MASK;
data[1] += (byte)pageNumber;
}
/**
If the page is a data page then this returns the number
of records stored in the data page.
@return - number of records in this page
*/
public int getNumberOfRecords()
{
return (((data[0] >> 7)& 1) << 1) | (data[1]>>7 &1);
}
/**
If the page is a header page then this returns the number
of bytes ina record that appears in this heap file.
@return - number of bytes in a record
*/
public int getRecordSize()
{
return getNumberOfRecords() + 1;
}
/**
Used in a header page of a heap file to indicate the size of
records stored in the file.
@param recordSize - size of the records in this heap file in bytes
*/
public void setRecordSize(int recordSize)
{
--recordSize;
setNumberOfRecords(recordSize);
}
/**
Used in a data page of a heap file to set the value of the number of
records currently stored in the page.
@param number - what value to set it to
*/
public void setNumberOfRecords(int number)
{
isValidNumber(number, 0, DATA_SIZE -1);
data[0] &= 127;
data[1] &= 127;
data[0] |= (number & 2)<< 6;
data[1] |= ( number & 1) << 7;
}
/**
Returns the given index byte from the bytes stored on page
@param byteNumber - index of byte to return
@return - a byte from page
*/
public byte getByte(int byteNumber)
{
isValidNumber(byteNumber, 0, PAGE_SIZE-1);
return data[byteNumber];
}
/**
Sets the value of the specified byte of this page
@param byteNumber - index of byte to set
@param value - value to set that byte to
*/
public void setByte(int byteNumber, byte value)
{
isValidNumber(byteNumber, 0, PAGE_SIZE-1);
data[byteNumber] = value;
}
/**
Generates from byte i of the bytes in this page a
String of representating the settings of the indiviual bits
in this byte.
@return string representation of the requested byte
*/
public String toStringByte(int i)
{
isValidNumber(i, 0, PAGE_SIZE-1);
int b = getByte(i);
String out = "";
for(int j = 1; j <= 128; j <<= 1)
{
if( (b & j) > 0)
{
out += " 1";
}
else
{
out += " 0";
}
}
return out;
}
/**
Generates a string that gives informations about the contents
of the page assuming the page is the data page of some heap file
@return - string with information
*/
public String toStringDataPage()
{
String out ="";
out += "Next Page: "+ getNextPage();
out += " Previous Page: " + getPreviousPage();
out += " Record Cnt: " + getNumberOfRecords();
out += " Data: [";
for(int j = DATA_START; j < PAGE_SIZE; j++)
{
int b = getByte(j) & 255;
out += " "+ b;
}
out += " ]";
return out;
}
/**
Generates a string that gives informations about the contents
of the page assuming the page is the header page of some heap file
@return - string with information
*/
public String toStringHeaderPage()
{
String out = "Name: ";
for(int i = DATA_START ; i < PAGE_SIZE - 2; i++)
{
out += (char)getByte(i);
}
out += " Next Page: "+ getNextPage();
out += " Previous Page: " + getPreviousPage();
out += " Record Size: " + getRecordSize();
out += " Available List Link:" + (getByte(PAGE_SIZE - 2) & 255);
out += " Full List Link:" + (getByte(PAGE_SIZE - 1) & 255);
return out;
}
/**
Checks if number is <=high and >= low. If not throws an
IndexOutofBoundsException. Method says which class it belongs
to (maybe could have avoided code duplication)
@param number - number to check
@param low - low value of range number should be in
@param high - high value of range number should be in
@throws IndexOutOfBoundsException - returned if number not in range
*/
static void isValidNumber(int number, int low, int high)
throws IndexOutOfBoundsException
{
if(number > high || number < low)
throw new IndexOutOfBoundsException("(Page Index Exception) Number was:"
+ number +".\n Maximum allowable is: " + high +
".\n Minimum allowable is: " + low + ".\n");
}
public static int PAGE_SIZE=6; //number of bytes in a page
public static int DATA_SIZE=4; // number of bytes of data in a page
// (ignoring next and previous links)
public static int DATA_START = PAGE_SIZE - DATA_SIZE ;
//byte offset to first byte of data
public static int MAX_PAGE_INDEX=127;
// maximum number that can occur
// in a next and previous link
public static int MASK=128; // used to select for the high order bit of a byte;
byte[] data; // actual data stored in page
}
Point Breakdown
|